package algorithm.shipinke;

import algorithm.leetcode.TreeNode;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

/**
 * 二叉树的前序中序和后序遍历
 */

public class TraverseTree {

    public void preorderTraverse(TreeNode root) {
        /**
         * 前序遍历, 根->左->右的顺序
         */
        if (root == null) return;
        System.out.println(root);
        preorderTraverse(root.left);
        preorderTraverse(root.right);
    }

    public void inorderTraverse(TreeNode root) {
        /**
         * 中序遍历, 左->中->右顺序
         */
        if (root == null) return;
        inorderTraverse(root.left);
        System.out.println(root);
        inorderTraverse(root.right);
    }

    public void postorderTraverse(TreeNode root) {
        /**
         * 后序遍历, 左->右->中
         */
        if (root == null) return;
        postorderTraverse(root.left);
        postorderTraverse(root.right);
        System.out.println(root);
    }

    public void houxu3(TreeNode t)// q1和q2 q1要先右后左，先遍历右侧，q1先装右侧就把右侧放到前面，左侧放在上面（栈顶）
    {
        /**
         * 前序遍历放入stack1,取出时(再放入stack2)顺序相反,再从stack2中取出又反了一次
         */
        Stack<TreeNode> q1 = new Stack<>();
        Stack<TreeNode> q2 = new Stack<>();
        if (t == null)
            return;
        q1.push(t);
        while (!q1.isEmpty()) {
            TreeNode t1 = q1.pop();
            q2.push(t1);

            if (t1.left != null) {
                q1.push(t1.left);
            }
            if (t1.right != null) {
                q1.push(t1.right);
            }
        }
        while (!q2.isEmpty()) {
            TreeNode t1 = q2.pop();
            System.out.print(t1.val + " ");
        }
    }


    public static void dfs(TreeNode node) {
        if (node == null) return;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(node);

        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            // 执行你的操作
            System.out.println(pop);

            // 注意要先左子树的话一定要先添加右子树,这个是细节
            if (pop.right != null) stack.push(pop.right);
            if (pop.left != null) stack.push(pop.left);
        }

    }

    public static void bfs(TreeNode node) {
        if (node == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(node);

        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            // 执行你的操作
            System.out.println(poll);

            if (poll.left != null) queue.add(poll.left);
            if (poll.right != null) queue.add(poll.right);
        }

    }

    /**
     * 不递归中序遍历树,注意返回是树的内容,树的结构已经改变
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        // 注意这个返回是整数而不是node,有点微妙,提示可能要改变树的结构
        LinkedList<Integer> result = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        if (root != null) stack.push(root);

        // 针对每个栈顶的节点:
        // 左子树有:压栈左子树,此节点左子树改为null
        // 左子树没有:
        //    右子树有:pop,push右子树
        //    右子树有:pop
        while (!stack.isEmpty()) {
            TreeNode peek = stack.peek();
            if (peek.left != null) {
                stack.push(peek.left);
                peek.left = null;
            } else {
                peek = stack.pop();
                result.add(peek.val);
                if (peek.right != null) stack.push(peek.right);
            }
        }

        return result;
    }


    public static void main(String[] args) {
        TreeNode a = new TreeNode("a"), b = new TreeNode("b"), c = new TreeNode("c"), d = new TreeNode("d"), e = new TreeNode("e"),
                f = new TreeNode("f"), g = new TreeNode("g");
        g.left = e;
        g.right = f;
        e.left = c;
        e.right = d;
        c.left = a;
        c.right = b;

        dfs(g);
        System.out.println("------------------------------");
        bfs(g);
    }

    // public static void main(String[] args) {
    //     TreeNode a = new TreeNode(6), b = new TreeNode(7), c = new TreeNode(4), d = new TreeNode(5), e = new TreeNode(2),
    //             f = new TreeNode(3), g = new TreeNode(1);
    //     g.left = e;
    //     g.right = f;
    //     e.left = c;
    //     e.right = d;
    //     c.left = a;
    //     c.right = b;
    //     TraverseTree solution = new TraverseTree();
    //     solution.postorderTraverse(g);
    //     System.out.println("-------------------");
    //     solution.houxu3(g);
    //
    // }
}
